package com.sheng.leetcode.year2022.month04.day01;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/04/01
 *
 * 954. 二倍数对数组
 *
 * 给定一个长度为偶数的整数数组 arr，
 * 只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；
 * 否则，返回 false。
 *
 * 示例 1：
 *
 * 输入：arr = [3,1,3,6]
 * 输出：false
 * 示例 2：
 *
 * 输入：arr = [2,1,2,6]
 * 输出：false
 * 示例 3：
 *
 * 输入：arr = [4,-2,2,-4]
 * 输出：true
 * 解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
 *
 * 提示：
 *
 * 0 <= arr.length <= 3 * 104
 * arr.length 是偶数
 * -105 <= arr[i] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0954 {

    @Test
    public void test01(){
        //int[] arr = {3,1,3,6};
        //int[] arr = {2,1,2,6};
        //int[] arr = {4,-2,2,-4};
        int[] arr = {2,1,2,1,1,1,2,2};
        System.out.println(new Solution().canReorderDoubled(arr));
    }
}
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr) {
            //记录每一个值的数量
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        if (map.getOrDefault(0, 0) % 2 != 0) {
            return false;
        }
        List<Integer> integers = new ArrayList<>();
        for (Integer integer : map.keySet()) {
            integers.add(integer);
        }
        Collections.sort(integers, (a, b) -> Math.abs(a) - Math.abs(b));
        for (Integer integer : integers) {
            if (map.getOrDefault(2 * integer, 0) < map.get(integer)) {
                return false;
            }
            map.put(2 * integer, map.getOrDefault((2 * integer), 0) - map.get(integer));
        }
        return true;
        /*quickSort(arr, 0, arr.length - 1);
        printArray(arr);
        return isReorderDoubled(arr);*/
    }

    // 数组遍历
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i == arr.length - 1) {
                System.out.print(arr[i]);
            } else {
                System.out.print(arr[i] + ", ");
            }
        }
        System.out.println("]");
    }

    // 快速排序法 quickSort()+partition()
    // 一次划分算法
    public static int partition(int r[], int first, int end) {
        int i = first; // 指向头
        int j = end; // 指向尾
        int temp = 0; // 辅助变量
        while (i < j) // i==j时跳出循环
        {
            while (i < j && r[i] < r[j]) // 右侧扫描
                j--;
            if (i < j) {
                temp = r[i];
                r[i] = r[j];
                r[j] = temp;
                i++;
            }
            while (i < j && r[i] < r[j]) // 左侧扫描
                i++;
            if (i < j) {
                temp = r[i];
                r[i] = r[j];
                r[j] = temp;
                j--;
            }
        }
        return i;
    }

    // 快速排序递归算法
    public static void quickSort(int r[], int first, int end) {
        int pivot = 0;
        if (first < end) {
            pivot = partition(r, first, end);
            quickSort(r, first, pivot - 1); // 前半部分递归
            quickSort(r, pivot + 1, end); // 后半部分递归
        }
    }

    public boolean isReorderDoubled(int[] arr) {
        boolean flag = true;
        int n = arr.length / 2;
        for (int i = 0; i < n; i++) {
            if (arr[2 * i + 1] < 0) {
                if (2 * arr[2 * i + 1] != arr[2 * i]) {
                    flag = false;
                }
            } else {
                if (arr[2 * i + 1] != 2 * arr[2 * i]) {
                    flag = false;
                }
            }
        }
        return flag;
    }
}
